package EstructurasDeDatos;
import java.util.ArrayList;
import java.util.List;


public class Arbol {
	protected String id;
	protected List<Arbol> hijos;
	protected int posX, posY;
	protected boolean marcado;
	
	public Arbol(String raiz){
		hijos=new ArrayList<Arbol>();
		id=raiz;
		marcado = false;
	}
	
	public Arbol(String raiz,List<Arbol> sons){
		hijos=sons;
		id=raiz;
		marcado = false;
	}
	
	public void agregarHijo(Arbol a){
		hijos.add(a);
	}
	
	public void agregarHijos(List<Arbol> sons){
		hijos.addAll(sons);
	}
	
	public Arbol getRaiz(){
		return this;
	}
	
	public String getId(){
		return id;
	}
	
	public void setId(String newId){
		id=newId;
	}
	
	public List<Arbol> getHijos(){
		return hijos;
	}
	
	public void setX(int x){
		posX = x;
	}
	
	public int getX(){
		return posX;
	}
	
	public void setY(int y){
		posY = y;
	}
	
	public int getY(){
		return posY;
	}
	
	public void marcar(){
		marcado=true;
	}
	
	public void desmarcar(){
		marcado=false;
	}
	
	public boolean getMarcado(){
		return marcado;
	}
	
	public int setearPosiciones(int xActual,int sepHorizontal,int nivelActual, int sepVertical){
		Integer xSig = xActual;
		if(!hijos.isEmpty()){
			for(Arbol a : hijos){
				xSig = a.setearPosiciones(xSig,sepHorizontal,nivelActual+1,sepVertical) + 1;
			}
			// Si la cantidad de hijos era 1, toma la posicion del hijo
			if(hijos.size()==1){
				setX(hijos.get(0).getX());
				setY(nivelActual*sepVertical);
			}
			//Sino, toma la posicion media entre los dos hijos extremos
			else{
				int posicionRaiz = (hijos.get(0).getX() + hijos.get(hijos.size()-1).getX())/2;
				setX(posicionRaiz);
				setY(nivelActual*sepVertical);
			}
			//Devuelve el nivel en x del último hijo de la derecha
			return xSig-1;
		}
		else{
			setY(nivelActual*sepVertical);
			setX(xActual*sepHorizontal);
			return xActual;
		}
	}
	
	public int obtenerCantidadHojas(){
		int hojasHijos=0;
		if(!hijos.isEmpty()){
			for(Arbol a : hijos)
				hojasHijos+=a.obtenerCantidadHojas();
			return hojasHijos;
		}
		else
			return 1;
	}
	
	public int obtenerProfundidadMaxima(){
		List<Integer> profundidadesHijos=new ArrayList<Integer>();
		if(!hijos.isEmpty()){
			for(Arbol a : hijos){
				profundidadesHijos.add(a.obtenerProfundidadMaxima());
			}
			int maxEntreHijos = buscarMaximo(profundidadesHijos);
			return maxEntreHijos + 1;
		}
		else
			return 1;
	}
	
	private int buscarMaximo(List<Integer> lista){
		int maximo = 0;
		for(Integer i : lista)
			if(i > maximo)
				maximo = i;
		return maximo;
	}
	
	public Arbol getSubArbol(String id){
		Arbol aRetornar = null;
		if(this.getId() == id)
			aRetornar = this;
		else{
			if(!hijos.isEmpty())
				for(Arbol a : hijos){
					Arbol hijo = a.getSubArbol(id);
					if(hijo != null){
						aRetornar = hijo;
					}
				}
		}
		//Si soy hojao si ninguno de mis hijos contenia el subarbol modificado, aRetornar seguira siendo null.
		return aRetornar;
	}
	
	public Arbol removeSubArbol(Arbol arb){
		Arbol aRetornar = null;
		if(this.getId() == arb.getId())
			aRetornar = this;
		else{
			if(!hijos.isEmpty())
				for(Arbol a : hijos){
					Arbol hijo = a.removeSubArbol(arb);
					if(hijo != null){
						aRetornar = hijo;
					}
				}
			hijos.remove(aRetornar);
		}
		//Si soy hojao si ninguno de mis hijos contenia el subarbol modificado, aRetornar seguira siendo null.
		return aRetornar;
	}
	
	public List<String> getNombresNodos(){
		List<String> nombres = new ArrayList<String>();
		nombres.add(getId());
		if(!hijos.isEmpty())
			for(Arbol a : hijos){
				nombres.addAll(a.getNombresNodos());
			}
		return nombres;
	}
	
	public boolean estaDentroNodo(int x,int y){
		boolean esta = false;
		if(x > this.getX() && x < this.getX()+25 && y > this.getY() && y < this.getY()+25)
			esta = true;
		if(!hijos.isEmpty() && !esta)
			for(Arbol a : hijos)
				esta = esta || a.estaDentroNodo(x, y);
		return esta;
	}
	
	public Arbol getNodoClickeado(int x,int y){
		Arbol arb = null;
		if(x > this.getX() && x < this.getX()+25 && y > this.getY() && y < this.getY()+25)
			arb = this;
		if(!hijos.isEmpty() && arb == null)
			for(Arbol a : hijos){
				Arbol res = a.getNodoClickeado(x,y);
				if(res != null)
					arb = res;
			}
		return arb;
	}
	
	public String toString(){
		String s = getId();
		if(!hijos.isEmpty()){
			s+="<";
			for(Arbol a : hijos)
				s+=a.toString()+",";
			s=s.substring(0,s.length()-1);
			s+=">";
		}
		return s;
	}
	
	public List<String> listadoNodosPreorden(){
		List<String> nodes = new ArrayList<String>();
		if(!getMarcado()){
			nodes.add(getId());
			if(!hijos.isEmpty() && algunHijoDesmarcado())
				for(Arbol a : hijos){
					nodes.addAll(a.listadoNodosPreorden());
				}
		}
		return nodes;
	}
	
	public List<String> listadoNodosPosorden(){
		List<String> nodes = new ArrayList<String>();
		if(!getMarcado()){
			if(!hijos.isEmpty() && algunHijoDesmarcado())
				for(Arbol a : hijos){
					nodes.addAll(a.listadoNodosPosorden());
				}
			nodes.add(getId());
		}
		return nodes;
	}
	
	public List<String> listadoNodosInorden(){
		List<String> nodes = new ArrayList<String>();
		if(!getMarcado()){
			if(!hijos.isEmpty())
				nodes.addAll(hijos.get(0).listadoNodosInorden());
			nodes.add(getId());
			if(hijos.size()>1)
				for(int i=1;i<hijos.size();i++){
					nodes.addAll(hijos.get(i).listadoNodosInorden());
				}
		}
		return nodes;
	}
	
	public boolean esBinario(){
		return obtenerAmplitudMax() <= 2;
	}
	
	//Debe llamarse con nivel= 0
	public List<String> parentesisAnidadosPreorden(int nivel){
		List<String> nodes = new ArrayList<String>();
		if(nivel==0)
			nodes.add("(");
		if(!getMarcado())
			nodes.add(getId());
		else
			nodes.add("λ");
		if(!hijos.isEmpty()){
			nodes.add("(");
			for(Arbol a : hijos){
				nodes.addAll(a.parentesisAnidadosPreorden(nivel+1));
				if(hijos.indexOf(a)<(hijos.size()-1))
					nodes.add(",");
			}
			nodes.add(")");
		}
		if(nivel==0)
			nodes.add(")");
		return nodes;
	}
	
	//Debe llamarse con nivel= 0
	public List<String> parentesisAnidadosPosorden(int nivel){
		List<String> nodes = new ArrayList<String>();
		if(nivel==0)
			nodes.add("(");
		if(!hijos.isEmpty()){
			nodes.add("(");
			for(Arbol a : hijos){
				nodes.addAll(a.parentesisAnidadosPosorden(nivel+1));
				if(hijos.indexOf(a)<(hijos.size()-1))
					nodes.add(",");
			}
			nodes.add(")");
		}
		if(!getMarcado())
			nodes.add(getId());
		else
			nodes.add("λ");
		if(nivel==0)
			nodes.add(")");
		return nodes;
	}
	
	public boolean esHoja(String idNodo){
		boolean es = true;
		if (getId()==idNodo && hijos.size()!=0)
			es = false;
		else if(getId()!=idNodo)
			for(Arbol a : hijos)
				es = es && a.esHoja(idNodo);
		return es;	
	}
	
	public int obtenerAmplitudMax(){
		int amplitud = obtenerHijosDesmarcados().size();
		for(Arbol a : obtenerHijosDesmarcados()){
			int ampHijo = a.obtenerAmplitudMax();
			if(ampHijo > amplitud)
				amplitud = ampHijo;
		}
		return amplitud;
	}
	
	public boolean esCompleto(){
		boolean es = esCompletoRec(obtenerAmplitudMax(),obtenerAltura());
		return es;
	}
	
	private boolean esCompletoRec(int cantHijos,int altura){
		boolean es = (obtenerHijosDesmarcados().size() == cantHijos || (altura == 0 && obtenerHijosDesmarcados().size() == 0));
		if(es)
			for(Arbol a : obtenerHijosDesmarcados())
				es = es && a.esCompletoRec(cantHijos,altura-1);
		return es;
	}
	
	public int obtenerAltura(){
		int altura=0;
		if(hijos.size()!=0){
			for(Arbol a : hijos){
				int alturaHijo=a.obtenerAltura();
				if(alturaHijo > altura)
					altura=alturaHijo;
			}
			altura+=1;
		}
		return altura;
	}
	
	public List<String> nodosHoja(){
		List<String> nsh=new ArrayList<String>();
		if(hijos.isEmpty())
			nsh.add(getId());
		for(Arbol a : obtenerHijosDesmarcados())
			nsh.addAll(a.nodosHoja());
		return nsh;
	}
	
	public List<String> nodosInternos(){
		List<String> nsh=new ArrayList<String>();
		if(!hijos.isEmpty())
			nsh.add(getId());
		for(Arbol a : obtenerHijosDesmarcados())
			nsh.addAll(a.nodosInternos());
		return nsh;
	}
	
	public void espejarArbol(){
		List<Arbol> hijosReverse=new ArrayList<Arbol>();
		while(!hijos.isEmpty()){
			Arbol temp = hijos.remove(0);
			hijosReverse.add(0,temp);
		}
		hijos.addAll(hijosReverse);
		for(Arbol a : hijos)
			a.espejarArbol();
	}
	
	private boolean algunHijoDesmarcado(){
		boolean hijoDesm = false;
		for(Arbol a : hijos)
			if(!a.getMarcado()){
				hijoDesm = true;
				break;
			}
		return hijoDesm;
	}
	
	private List<Arbol> obtenerHijosDesmarcados(){
		List<Arbol> lista = new ArrayList<Arbol>();
		for(Arbol a : hijos){
			if(!a.getMarcado())
				lista.add(a);
		}
		return lista;
	}
	
	public boolean esHijoHojaUnico(Arbol arb){
		boolean es=false;
		if(getId()==arb.getId()){
			//Solo entra aquí si es el árbol principal.
			es = true;
		}
		else{
			es = esHijoHojaUnicoRec(arb.getId());
		}
		return es;
	}
	
	private boolean esHijoHojaUnicoRec(String idArb){
		boolean es = false;
		boolean loEncontre = false;
		List<Arbol> hijosDesm = obtenerHijosDesmarcados();
		for(Arbol a : hijosDesm){
			if(a.getId()==idArb)
				loEncontre = true;
		}
		if(!loEncontre){
			for(Arbol a : hijosDesm)
				es = es || a.esHijoHojaUnicoRec(idArb);
		}
		else{
			if(hijosDesm.size() < 2)
				es = true;
		}
		return es;
	}
	
	public void desmarcarHijosUnicos(){
		if(hijos.size()==1 && hijos.get(0).getMarcado())
			hijos.get(0).desmarcar();
		for(Arbol a : hijos){
			a.desmarcarHijosUnicos();
		}
	}
	
	public List<String> obtenerNodosVacios(){
		List<String> nodosVacios=new ArrayList<String>();
		if(getMarcado())
			nodosVacios.add(getId());
		for(Arbol a : hijos){
			nodosVacios.addAll(a.obtenerNodosVacios());
		}
		return nodosVacios;
	}
	
	public void marcarNodosVacios(List<String> nodosVacios){
		if(nodosVacios.contains(getId()))
			marcar();
		for(Arbol a : hijos)
			a.marcarNodosVacios(nodosVacios);
	}
	
}
